\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{amsmath}
\begin{document}
\begin{verbatim}
               胡宇梦       3210103435      信息与计算科学
\end{verbatim}
\section{对于二叉树各数据结构的理解}
（1）二叉搜索树

二叉搜索树节点的具体实现如下：
\begin{verbatim}
          struct BinaryNode{  
              Comparable element;
              BinaryNode *left;
              BinaryNode *right;};
\end{verbatim}

        二叉搜索树常用的操作有：MakeEmpty()、Find()、FindMin()、FindMax()、Insert()、Delete()。

（2）Avl树
本质仍是一棵二叉搜索树，只不过增加了平衡的要求，使树的高度在每次插入元素后仍能保持O(logn)级别，由于需要对每个结点计算平衡因子，因此
需要在树的结构中加入一个变量height，用来记录当前结点为根节点的子树的高度。其节点的具体实现如下：
\begin{verbatim}
          struct node{
          int data, height;
          node* left, right;  };
    \end{verbatim}
    （3）伸展树（SplayTree）
        伸展树是二叉查找树的改进，可以进行自我调整。当一个节点被访问后，它就要经过一系列AVL树的旋转被放到根上。
    它保证从空树开始任意连续M次对树的操作最多花费O(MlogN)时间。一棵伸展树每次操作的摊还代价是O(logN)
    伸展是一种特殊的旋转方式，它采用了类似于平衡二叉树的策略，展开有之字形和一字形两种。

    伸展树的节点实现与二叉搜索树完全一致。
\section{设计思路和测试结果（代码见头文件）}

    考虑到三种树的节点高度一致，所以可以将其抽象成一个Node类，三种树的节点类由Node派生。

    同时考虑到三种树本质都是二叉树，所以都具备二叉树应有的操作，比如MakeEmpty()、Find()、FindMin()、FindMax()、Insert()、Delete()
    等操作，将其抽象成BinaryTree类，三种树由此类派生。（PS：此次测试案例可以编译运行，但是BinaryTree只抽象了insert和remove操作）。

    下图为对三种树，插入、打印、删除操作的测试结果，测试成功。
    \begin{figure}[ht]
        \centering
        \includegraphics[width=3cm]{测试.png}
        \label{mode=1}
    \end{figure}  

    下图为三种树类的UML类图 ，
\begin{figure}[ht]
    \centering
    \includegraphics[width=8.4cm]{UML类图.png}
    \label{mode=1}
\end{figure}   



\end{document}
